#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int>> ret;
        int m = big.size();
        for (int i = 0; i < smalls.size(); i++) {
            string target = smalls[i];
            if (target == "") {
                ret.push_back({});
                continue;
            }
            int n = target.size();
            vector<int> tmp;
            for (int left = 0; left < m; left++) {
                int right = left + n - 1;
                if (right < m && target == big.substr(left, n)) {
                    tmp.push_back(left);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;

        int hash[26] = { 0 };
        for (int i = 0; i < s1.size(); i++) hash[s1[i] - 'a']++;

        for (int i = 0; i < s2.size(); i++) {
            hash[s2[i] - 'a']--;
            if (hash[s2[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = m - 1, y = 0;
        while (x >= 0 && y < n) {
            if (matrix[x][y] > target) {
                x--;
            }
            else if (matrix[x][y] < target) {
                y++;
            }
            else return true;
        }
        return false;
    }
};